package tree.binary_tree.traversal;

import tree.binary_tree.base.MyTree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的遍历:
 * 前中后序递归、非递归遍历
 * 层次遍历（广度优先遍历）
 * 深度优先遍历：前中后序遍历
 *
 * @author yeyangtao created at 17:09 2020/8/24
 */
public class MyTreeDemo {
    public static void main(String[] args) {
        MyTree<Integer> t1 = new MyTree<>(1);
        MyTree<Integer> t2 = new MyTree<>(2);
        MyTree<Integer> t3 = new MyTree<>(3);
        MyTree<Integer> t4 = new MyTree<>(4);

        t1.setLeft(t2);
        t1.setRight(t3);
        t2.setLeft(t4);

        System.out.println("前序");
        pre(t1);
        System.out.println();
        System.out.println("前序非递归");
        pre1(t1);
        System.out.println();

        System.out.println("中序");
        in(t1);
        System.out.println();
        System.out.println("中序非递归");
        in1(t1);
        System.out.println();

        System.out.println("后序");
        after(t1);
        System.out.println();
        System.out.println("后序非递归");
        after1(t1);
        System.out.println();

        System.out.println("层次");
        lever(t1);
        System.out.println();

        System.out.println("深度优先");
        dfs(t1);
    }

    /**
     * 前序遍历
     */
    public static void pre(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        System.out.print(root.getValue() + " ");
        pre(root.getLeft());
        pre(root.getRight());
    }

    /**
     * 前序遍历非递归方式
     */
    public static void pre1(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        //栈 push(at the head of this deque),
        // pop( removes and returns the first element of this deque),
        // peek(returns the first element of this deque)
        Deque<MyTree<Integer>> stack = new LinkedList<>();
        stack.push(root);
        MyTree<Integer> current;
        while (!stack.isEmpty()) {
            current = stack.pop();
            System.out.print(current.getValue() + " ");
            if (current.getRight() != null) {
                stack.push(current.getRight());
            }
            if (current.getLeft() != null) {
                stack.push(current.getLeft());
            }
        }
    }

    /**
     * 中序遍历
     */
    public static void in(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        in(root.getLeft());
        System.out.print(root.getValue() + " ");
        in(root.getRight());
    }

    /**
     * 中序遍历非递归
     * 1.先将根节点入栈
     * 2.将当前节点的所有左孩子入栈，直到左孩子为空
     * 3.访问栈顶元素，如果栈顶元素存在右孩子，则继续第2步
     * 4.重复第2、3步，直到栈为空并且所有的节点都被访问
     */
    public static void in1(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        Deque<MyTree<Integer>> stack = new LinkedList<>();
        MyTree<Integer> current = root;
        while (current != null || !stack.isEmpty()) {
            //1.根节点入栈
            //2.所有左节点入栈
            while (current != null) {
                stack.push(current);
                current = current.getLeft();
            }
            //3.访问栈顶
            current = stack.pop();
            System.out.print(current.getValue() + " ");
            //4.如果栈顶元素存在右孩子，则将右孩子赋值给tmp，也就是将右孩子入栈
            if (current.getRight() != null) {
                current = current.getRight();
                //否则，将tmp置为null，表示下次要访问的是栈顶元素
            } else {
                current = null;
            }
        }
    }

    /**
     * 后序遍历
     */
    public static void after(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        after(root.getLeft());
        after(root.getRight());
        System.out.print(root.getValue() + " ");
    }

    /**
     * 后序遍历非递归
     * 1.根节点入栈
     * 2.将根节点的左子树入栈，直到最左，没有左孩子为止
     * 3.得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，
     * 如果存在并且没有被访问，则将右孩子入栈，否则，就访问栈顶元素
     */
    public static void after1(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        Deque<MyTree<Integer>> stack = new ArrayDeque<>();
        MyTree<Integer> current = root;
        MyTree<Integer> prev = null;
        while (current != null || !stack.isEmpty()) {
            //1.根节点 及其左孩子入栈
            while (current != null) {
                stack.push(current);
                current = current.getLeft();
            }
            if (!stack.isEmpty()) {
                //2.获得栈顶
                current = stack.peek();
                //3.没有右孩子或右孩子被访问
                if (current.getRight() == null || current.getRight() == prev) {
                    //则可以访问栈顶
                    current = stack.pop();
                    System.out.print(current.getValue() + " ");
                    //标记上一次访问的节点
                    prev = current;
                    current = null;
                } else {
                    //4.存在没有访问的右孩子，继续进栈
                    current = current.getRight();
                }
            }
        }
    }

    /**
     * 层次遍历
     */
    public static void lever(MyTree<Integer> root) {
        if (null == root) {
            return;
        }
        //队列 offer,在队列尾部新增
        // poll,返回队列第一位并从队列中删除
        //peek，返回队列第一位不返回
        Queue<MyTree<Integer>> list = new LinkedList<>();
        list.offer(root);
        MyTree<Integer> current;
        while (!list.isEmpty()) {
            current = list.poll();
            System.out.print(current.getValue() + " ");
            if (current.getLeft() != null) {
                list.offer(current.getLeft());
            }
            if (current.getRight() != null) {
                list.offer(current.getRight());
            }
        }
    }

    /**
     * 深度优先遍历
     */
    public static void dfs(MyTree<Integer> root) {
        if (null == root) return;
        Deque<MyTree<Integer>> stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            MyTree<Integer> curr = stack.pop();
            System.out.print(curr.getValue() + " ");
            if (curr.getRight() != null) stack.push(curr.getRight());
            if (curr.getLeft() != null) stack.push(curr.getLeft());
        }
    }

}
